#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* begin & end are index */
void merge(int *input_arr, int begin1, int end1, int begin2, int end2, int *temp_arr)
{
    int index = begin1;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (input_arr[begin1] <= input_arr[begin2])
        {
            temp_arr[index++] = input_arr[begin1++];
        }
        else
        {
            temp_arr[index++] = input_arr[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        temp_arr[index++] = input_arr[begin1++];
    }
    while (begin2 <= end2)
    {
        temp_arr[index++] = input_arr[begin2++];
    }
    memcpy(input_arr, temp_arr, (end2 + 1) * sizeof(int));
    return;
}

void merge_sort(int *input_arr, int size, int *temp_arr)
{
    if (size <= 1)
    {
        return;
    }
    else
    {
        merge_sort(input_arr, size / 2, temp_arr);
        merge_sort(input_arr + size / 2, size - size / 2, temp_arr);
        merge(input_arr, 0, size / 2 - 1, size / 2, size - 1, temp_arr);
    }
    return;
}

int main(int argc, char* argv[])
{
    int i =0;
    int *input = (int*)malloc((argc - 1) * sizeof(int));
    for (i = 0; i < argc - 1; i++)
    {
        input[i] = atoi(argv[i + 1]);
    }

    int *temp_arr = (int*)malloc(sizeof(int) * (argc - 1));
    merge_sort(input, argc - 1, temp_arr);
    for (i = 0; i < argc - 1; i++)
    {
        printf("%d\n", input[i]);
    }
    free(temp_arr);
    return 0;
}